package com.gxc.linkedList;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 将搜索二叉树转换成双向链表
 */
public class TreeToLinkedList {

    /**
     * 1.树的中序遍历，获取有序的node
     * 2.node互相连接
     * @param root
     * @return
     */
    public DoubleNode handle(DoubleNode root) {
        Queue<DoubleNode> queue = new LinkedList<>();
        inOrderTraversal(root, queue);
        if (queue.isEmpty()) return root;

        DoubleNode prev = null;
        DoubleNode cur = null;
        DoubleNode head = queue.peek();
        while (!queue.isEmpty()) {
            cur = queue.poll();
            cur.left = prev;
            cur.right = queue.peek();
            prev = cur;
        }
        return head;
    }

    /**
     * 递归中序遍历
     * @param node
     * @param queue
     */
    private void inOrderTraversal(DoubleNode node, Queue<DoubleNode> queue) {
        if (node == null) return;

        inOrderTraversal(node.left, queue);
        queue.offer(node);
        inOrderTraversal(node.right, queue);
    }

    /**
     * 非递归中序遍历
     * @param node
     * @param queue
     */
    private void inOrderTraversal2(DoubleNode node, Queue<DoubleNode> queue) {
        if (node == null) return;

        Stack<DoubleNode> stack = new Stack<>();
        DoubleNode cur = node;
        //当前cur不为空，或者栈不为空
        while (cur!=null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                queue.offer(cur);
                cur = cur.right;
            }
        }
    }

    public DoubleNode handle2(DoubleNode root) {
        if (root == null) return root;

        return recursion(root).start;
    }

    public ReturnType recursion(DoubleNode node) {
        if (node == null) return null;

        ReturnType left = recursion(node.left);
        ReturnType right = recursion(node.right);

        DoubleNode start = node;
        DoubleNode end = node;
        if (left != null) {
            left.end.right = node;
            node.left = left.end;
            start = left.start;
        }
        if (right != null) {
            node.right = right.start;
            right.start.left = node;
            end = right.end;
        }
        return new ReturnType(start, end);
    }

    public ReturnType recursion2(DoubleNode node) {
        if (node == null) return new ReturnType(null, null);

        ReturnType left = recursion(node.left);
        ReturnType right = recursion(node.right);

        if (left.end != null) {
            left.end.right = node;
        }
        node.left = left.end;
        node.right = right.start;
        if (right.start != null) {
            right.start.left = node;
        }
        return new ReturnType(left.start!=null?left.start:node, right.end!=null?right.end:node);
    }

    public class ReturnType {
        public DoubleNode start;
        public DoubleNode end;

        public ReturnType(DoubleNode start, DoubleNode end) {
            this.start = start;
            this.end = end;
        }
    }
}
